package tree;

/**
 * 解题思路：
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-kcb0/
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
 * 对于二叉树中的一个节点，所能贡献的最大值为该节点的值和左右子节点的最大值，如果子节点的值为正，可以计入在内，否则不计入。
 * 维护一个全局变量maxValue来保存最大路径和，在递归的过程中更新值。
 */

public class MaxPathSum_124 {
    // 可能是负数，所以取最小值
    private int maxValue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getMaxValueOnOneNode(root);
        return maxValue;
    }

    /**
     * 计算寄一个节点的最大的贡献值
     * @param root
     * @return
     */
    public int getMaxValueOnOneNode(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 分别计算节点的左右子树能提供的最大贡献值，如果是负数就看做0
        int left = Math.max(0, getMaxValueOnOneNode(root.left));
        int right = Math.max(0, getMaxValueOnOneNode(root.right));

        // 更新最大路径和
        maxValue = Math.max(maxValue, left + right + root.val);
        // 返回节点的最大贡献值，记得加上root.val
        return Math.max(left + root.val, right + root.val);
    }
}
